| Authors |
Popkov Kirill Andreevich, Candidate of physical and mathematical sciences, researcher, sector of theoretical cybernetics of the department No. 4, Keldysh Institute of Applied Mathematics (Russian Academy of Sciences) (4, Miusskaya square, Moscow, Russia), E-mail: kirill-formulist@mail.ru
|
| Abstract |
Background. We study the possibility of constructing of (two-pole) contact circuits which implement Boolean functions on n variables and allow short complete diagnostic tests regarding contact breaks and/or closures. The topic under study relates to the problem of synthesis of easily testable circuits, set by S. V. Yablonskiy and I. A. Chegis in the 50s of the last century and well studied by now.
Materials and methods. We prove lower estimates of test lengths by selecting of contact faults, under which the resulting fault functions of an arbitrary contact circuit implementing a given Boolean function differ from each other on no more than two vectors. At that, some classes of ``the most difficult'' Boolean functions for testing in terms of the lengths of minimal complete diagnostic tests are well described using the concepts of maximal independent set in the Boolean cube graph, as well as binary block code correcting one error. We use contact circuits modeling representations of Boolean functions by disjunctive or conjunctive normal forms to prove the upper bounds of the test lengths.
Results. We prove that any Boolean function on n variables can be implemented by a contact circuit allowing a complete diagnostic test with length not more than 2n−1 regarding contact breaks; the same fact is also true regarding contact closures. In three cases: under contact breaks and closures, only under their breaks or only under their closures, we find rather extensive classes of Boolean functions on n variables, for each of which the length of the minimal complete diagnostic test at its implementation by contact circuits is the maximal possible among all Boolean functions on n variables and equals 2n , 2n−1 , 2n−1 , respectively. We obtain overexponential lower bounds on the number of Boolean functions from each of these classes.
Conclusions. The upper bounds on the lengths of the minimal complete diagnostic tests of contact break and contact closure for an arbitrary Boolean function at its implementation by contact circuits are improved. Some classes of ``the most difficult'' functions for testing are described.
|
| Key words |
contact circuit, contact break, contact closure, complete diagnostic test, Boolean function, maximal independent set, binary block code
|
| References |
1. Лупанов, О. Б. Асимптотические оценки сложности управляющих систем / О. Б. Лупанов. – Москва : Изд-во МГУ, 1984. – 138 с.
2. Чегис, И. А. Логические способы контроля работы электрических схем / И. А. Чегис, С. В. Яблонский // Труды Математического института имени В. А. Стеклова. – 1958. – Т. 51. – С. 270–360.
3. Яблонский, С. В. Надежность и контроль управляющих систем / С. В. Яблонский // Материалы Всесоюзного семинара по дискретной математике и ее приложениям (Москва, 31 января – 2 февраля 1984 г.). – Москва : МГУ, 1986. – С. 7–12.
4. Яблонский, С. В. Некоторые вопросы надежности и контроля управляющих систем / С. В. Яблонский // Математические вопросы кибернетики. – Вып. 1. – Москва : Наука, 1988. – С. 5–25.
5. Редькин, Н. П. Надежность и диагностика схем / Н. П. Редькин. – Москва : Изд-во МГУ, 1992. – 192 с.
6. Мадатян, Х . А. Полный тест для бесповторных контактных схем / Х. А. Мадатян // Проблемы кибернетики. – Вып. 23. – Москва : Наука, 1970. – С. 103–118.
7. Редькин, Н. П. О диагностических тестах для контактных схем / Н. П. Редькин // Вестник Московского университета. Сер. 1, Математика. Механика. – 2019. – № 2. – С. 35–37.
8. Редькин, Н. П. О полных проверяющих тестах для контактных схем / Н. П. Редькин // Методы дискретного анализа в исследовании экстремальных структур. – Вып. 39. – Новосибирск : Изд-во ИМ СО АН СССР, 1983. – С. 80–87.
9. Редькин, Н. П. О проверяющих тестах замыкания и размыкания / Н. П. Редькин // Методы дискретного анализа в оптимизации управляющих систем. – Вып. 40. – Новосибирск : Изд-во ИМ СО АН СССР, 1983. – С. 87–99.
10. Романов, Д. С. О синтезе контактных схем, допускающих короткие проверяющие тесты / Д. С. Романов // Ученые записки Казанского университета. Физико-математические науки. – 2014. – Т. 156, кн. 3. – С. 110–115.
11. Попков, К. А. О тестах замыкания для контактных схем / К. А. Попков // Дискретная математика. – 2016. – Т. 28, № 1. – С. 87–100.
12. Попков, К. А. О проверяющих тестах размыкания для контактных схем / К. А. Попков // Дискретная математика. – 2017. – Т. 29, № 4. – С. 66–86.
13. Попков, К. А. О диагностических тестах размыкания для контактных схем / К. А. Попков // Дискретная математика. – 2019. – Т. 31, № 2. – С. 123–142.
14. Duffus, D. Maximal independent sets in the covering graph of the cube / D. Duffus, P. Frankl, V. Rödl // Discrete Applied Mathematics. – 2013. – № 161. – P. 1203–1208.
15. Ложкин, С. А. Лекции по основам кибернетики : учеб. пособие для студентов / С. А. Ложкин. – Москва : Изд. отдел ф-та ВМиК МГУ, 2004. – 251 с.
16. Питерсон, У. Коды, исправляющие ошибки / У. Питерсон, Э. Уэлдон. – Москва : Мир, 1976. – 593 с.
17. Яблонский, С. В. Введение в дискретную математику / С. В. Яблонский. – Москва : Наука, 1986. – 384 с.
|
